import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

//目标a+b+c=0
//第二轮遍历
// a+b+c>0  右指针左移
// a+b+c>0  左指针左移
//如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 c 满足 a+b+c=0。当第二重循环往后枚举一个元素 b时，
// 由于 b ′>b，那么满足 a+b ′+c ′=0 的 c ′一定有 c ′<c，即 c ′在数组中一定出现在 c 的左侧。
// 也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。
public class test15 {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++) {
            //重复则跳过
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int k = nums.length - 1;
            for (int j = i + 1; j < k; j++) {
                //重复则跳过
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                //和>0则跳过
                while (nums[i] + nums[j] + nums[k] > 0 && j < k) {
                    k--;
                }
                if (j == k) break;
                if (nums[i] + nums[j] + nums[k] == 0) {
                    ans.add(Arrays.asList(nums[i], nums[j], nums[k]));
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        //System.out.println(new test15().threeSum(new int[]{1, 2, 3, 4}));//[]
//        System.out.println(new test15().threeSum(new int[]{-1, 0, 1, 2, -1, -4}));//[[-1, -1, 2], [-1, 0, 1]]
//        System.out.println(new test15().threeSum(new int[]{0,1,1}));//[]
//        System.out.println(new test15().threeSum(new int[]{0,0,0}));//[[0, 0, 0]]
//        System.out.println(new test15().threeSum(new int[]{1,2,-2,-1}));
//        System.out.println(new test15().threeSum(new int[]{0, 1, 1}));//[]


        System.out.println(new test15().threeSum(new int[]{-1,0,1,2,-1,-4,-2,-3,3,0,4}));//[]

//        测试用例:[-1,0,1,2,-1,-4,-2,-3,3,0,4]
//        测试结果:[[-4,0,4],[-4,1,3],[-3,1,2],[-2,0,2],[-1,0,1]]
//        期望结果:[[-4,0,4],[-4,1,3],[-3,-1,4],[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]

    }
}
